class FSM(object):
    def __init__(self, instructions):
        states = dict()
        for x in instructions.split('\n'):
            name, transmit, output = x.split(';')
            transmits = transmit.strip().split(',')
            states[name] = dict()
            states[name]['name'] = name
            states[name][0] = transmits[0].strip()
            states[name][1] = transmits[1].strip()
            states[name]['out'] = int(output.strip())
        self.states = states

    def run_fsm(self, start, sequence):
        path = [start]
        cur_state = self.states[start]
        for x in sequence:
            next_st_name = cur_state[x]
            path.append(next_st_name)
            cur_state = self.states[next_st_name]
        return (cur_state['name'], cur_state['out'], path)
